package com.jp.algorithm.dp;

public class Package01 {
    static int staticMax=0;

    public static int getMax(int[][] things,int k, int weight){

        if(k==0)
            return things[k][1];
        int max=0;
        for(int i=k-1;i>=0;i--){
            if(things[i][0] <= weight-things[k][0])
            {
                int m=getMax(things,i,weight-things[k][0]);
                if(m>max)
                    max=m;
            }

        }
        if(max+things[k][1] > staticMax)
            staticMax=max+things[k][1];
        return max+things[k][1];
    }

    public static void test(){
        int[][] things ={{1,1500},{4,3000},{3,2000},{1,2000}};
        getMax(things,things.length-1,4);
        System.out.println(staticMax);
    }

    public static void main(String[] args) {
        test();
    }
}
